//Wed Jun  8 16:31:10 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

class NumberLabyrinthDiv2 {
public:
	int getMinimumNumberOfMoves(vector <string>, int, int, int, int, int);
	bool checkBound(int x, int y);
	int grid[51][51][51];
	int M;
	int N;
};

int NumberLabyrinthDiv2::getMinimumNumberOfMoves(vector <string> board, int r1, int c1, int r2, int c2, int K) {
	M = board.size();
	N = board[0].size();
	memset(grid, -1, sizeof(grid));

	deque<pair<pair<int, int>, int> > q;
	q.push_back(make_pair(make_pair(r1, c1), K));
	grid[r1][c1][K] = 0;
	while(!q.empty()){
		int x = q.front().first.first;
		int y = q.front().first.second;
		int k = q.front().second;
		q.pop_front();
		if(r2 == x && c2 == y) continue;
		if(board[x][y] == '.' ){
			if(k>0)
				for(int i=0; i<4; i++){
					for(int j=1; j<=9; j++){
						int xx = x + dx[i] * j;
						int yy = y + dy[i] * j;
						if(checkBound(xx, yy) && grid[xx][yy][k-1] == -1){
							grid[xx][yy][k-1] = grid[x][y][k] + 1; //j;
							q.push_back(make_pair(make_pair(xx, yy), k-1));
						}
					}
				}
		}
		else{
			int j = board[x][y] - '0';
			if(j > 0)
				for(int i=0; i<4; i++){
					int xx = x + dx[i] * j;
					int yy = y + dy[i] * j;
					if(checkBound(xx, yy) && grid[xx][yy][k] == -1){
						grid[xx][yy][k] = grid[x][y][k] + 1; //(board[x][y] - '0');
						q.push_back(make_pair(make_pair(xx, yy), k));
					}
				}
		}
	}
	int ret = -1;
	for(int i=0; i<=K; i++){
		if( grid[r2][c2][i]!=-1){
			if(ret == -1 || grid[r2][c2][i] < ret){
				ret = grid[r2][c2][i];
			}
		}
	}
	return ret;
}

bool NumberLabyrinthDiv2::checkBound(int x, int y){
	return x>=0 && x<M && y>=0 && y<N;
}

//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!
